package algorithm.swordoff;
//
//import java.util.HashMap;
//import java.util.Map;

/**
 * 复杂链表的复制
 */

//public class SQ35 {
//    public Node copyRandomList(Node head) {
//        // 1. 若头节点 head 为空节点，直接返回 null
//        if(head == null) return null;
//        // 2. 初始化:哈希表 节点 cur 指向头节点
//        Node cur = head;
//        Map<Node, Node> map = new HashMap<>();
//        // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
//        while(cur != null) {
//            map.put(cur, new Node(cur.val));
//            cur = cur.next;
//        }
//        cur = head;
//        // 4. 构建新链表的 next 和 random 指向
//        while(cur != null) {
//            map.get(cur).next = map.get(cur.next);
//            map.get(cur).random = map.get(cur.random);
//            cur = cur.next;
//        }
//        // 5. 返回新链表的头节点
//        return map.get(head);
//
//    }
//
//}
//
//
//class Node {
//    int val;
//    Node next;
//    Node random;
//
//    public Node(int val) {
//        this.val = val;
//        this.next = null;
//        this.random = null;
//    }
//}